package com.lun.medium;

import java.util.HashMap;

import com.lun.util.BinaryTree.TreeNode;

public class PathSumIII {
	
	//方法一：我写的，暴力算法 + DFS
    public int pathSum(TreeNode root, int targetSum) {
    	int[] findCount = {0};
    	dfs(root, findCount, targetSum);
        return findCount[0];
    }
    
    private void dfs(TreeNode node, int[] findCount, int targetSum) {
    	if(node == null) return;
    	
    	dfs2(node, 0, findCount, targetSum);
    	
    	dfs(node.left, findCount, targetSum);
    	dfs(node.right, findCount, targetSum);
    }
    
    private void dfs2(TreeNode node, int sum, int[] findCount, int targetSum) {
    	if(node == null) return;
    	
    	if((sum += node.val) == targetSum)
    		findCount[0]++;
    	
    	dfs2(node.left, sum, findCount, targetSum);
    	dfs2(node.right, sum, findCount, targetSum);
    }
    
    //方法二：别人写的，暴力算法 + DFS
    public int pathSum2(TreeNode root, int sum) {
        if (root == null) return 0;
        return pathSumFrom(root, sum) + pathSum2(root.left, sum) + pathSum2(root.right, sum);
    }
    
    private int pathSumFrom(TreeNode node, int sum) {
        if (node == null) return 0;
        return (node.val == sum ? 1 : 0) 
            + pathSumFrom(node.left, sum - node.val) + pathSumFrom(node.right, sum - node.val);
    }
    
    
    //方法三：别人写的，利用缓存，空间换时间
    public int pathSum3(TreeNode root, int sum) {
        HashMap<Integer, Integer> preSumMap = new HashMap<>();
        preSumMap.put(0,1);
        int[] count = {0};
        helper(root, 0, sum, preSumMap, count);
        return count[0];
    }
    
    public void helper(TreeNode root, int currSum, int target, HashMap<Integer, Integer> preSumMap, int[] count) {
        if (root == null)
            return;
        
        currSum += root.val;

        if (preSumMap.containsKey(currSum - target)) {
            count[0] += preSumMap.get(currSum - target);
        }
        
        if (!preSumMap.containsKey(currSum)) {
            preSumMap.put(currSum, 1);
        } else {
            preSumMap.put(currSum, preSumMap.get(currSum) + 1);
        }
        
        helper(root.left, currSum, target, preSumMap, count);
        helper(root.right, currSum, target, preSumMap, count);
        preSumMap.put(currSum, preSumMap.get(currSum) - 1);
    }
    
    //方法四：方法三的另一种写法
    public int pathSum4(TreeNode root, int sum) {
        if (root == null) return 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);//初始值，当sum-target==0成立, 计数+1
        return findPathSum(root, 0, sum, map);  
    }
    
    private int findPathSum(TreeNode curr, int sum, int target, HashMap<Integer, Integer> map) {
        if (curr == null)
            return 0;
        
        // update the prefix sum by adding the current val
        sum += curr.val;
        
        // get the number of valid path, ended by the current node
        int numPathToCurr = map.getOrDefault(sum - target, 0); 
        
        // update the map with the current sum, so the map is good to be passed to the next recursion
        map.put(sum, map.getOrDefault(sum, 0) + 1);
        
        // add the 3 parts discussed in 8. together
        int res = numPathToCurr + findPathSum(curr.left, sum, target, map)
                                               + findPathSum(curr.right, sum, target, map);
        // restore the map, as the recursion goes from the bottom to the top
        map.put(sum, map.get(sum) - 1);
        return res;
    }
    
}
